import java.util.*;
class Solution {
    //648. 单词替换

    public String replaceWords(List<String> dictionary, String sentence) {
        String[] s = sentence.split(" ");
        StringBuilder ans = new StringBuilder();
        HashSet<String> set = new HashSet<>();
        for(int i=0;i<dictionary.size();i++){
            set.add(dictionary.get(i));
        }
        for(int i=0;i<s.length;i++){
            String tmp = s[i];
            if(i==s.length-1){
                ans.append(func(tmp,set));
            }else{
                ans.append(func(tmp,set)).append(" ");
            }
        }
        return ans.toString();
    }
    public static String func(String s,HashSet<String> set){
        StringBuilder tmp = new StringBuilder();
        for(int i=0;i<s.length();i++){
            tmp.append(s.charAt(i));
            if(set.contains(tmp.toString())){
                return tmp.toString();
            }
        }
        return s;
    }
}





//1705. 吃苹果的最大数目
class Solution1{
    public int eatenApples(int[] apples, int[] days) {
        int res = 0;
        int len = apples.length;

        // 计算最后一个苹果可能腐烂的最晚时间
        for (int i = 0; i < days.length; i++) {
            len = Math.max(len, days[i] + i);
        }

        // 记录每天会腐烂的苹果数量
        int[] count = new int[len];
        // 记录当前库存中最早腐烂的苹果是哪一天
        int idx = len;

        for (int i = 0; i < apples.length; i++) {
            // 确保 idx 至少从当前天开始
            idx = Math.max(idx, i);

            if (apples[i] > 0) {
                // 计算当前苹果的最后可食用日
                // 苹果在 days[i] 天后腐烂，所以它的最后可食用日是 i + days[i] - 1
                int expireDay = i + days[i] - 1;
                count[expireDay] += apples[i];
                // 更新当前最早腐烂的苹果天数
                idx = Math.min(idx, expireDay);
            }

            // 找到最近还没腐烂并且有库存的苹果
            while (idx < len && count[idx] == 0) {
                idx++;
            }

            // 如果没有可食用的苹果，跳过
            if (idx == len) {
                continue;
            }

            // 吃掉一个最近即将腐烂的苹果
            res++;
            count[idx]--;
        }

        // 处理所有剩余的苹果
        int start = apples.length;
        while (idx < len) {
            if (count[idx] > 0) {
                // 计算还能吃几天
                int daysToEat = idx - start + 1;
                if (count[idx] >= daysToEat) {
                    res += daysToEat;
                    start = idx + 1;
                } else {
                    res += count[idx];
                    start += count[idx];
                }
            }
            idx++;
        }

        return res;
    }
}
